package datastructure.ch03_linked.ch04_dummyhead;

/**
 * 单向循环链表
 *
 * @author guodd
 * @version 1.0 use jdk 1.8
 */
public class LinkedListDummy<E> {
    public static void main(String[] args) {
        LinkedListDummy<Integer> obj = new LinkedListDummy<>();
        obj.addFirst(4);
        obj.addFirst(3);
        obj.addFirst(2);
        obj.addFirst(1);
        obj.add(2, 0);
        System.out.println(obj);
    }

    int size;
    Node<E> dummyHead;

    public LinkedListDummy() {
        size = 0;
        dummyHead = new Node<>();
    }

    private static class Node<E> {
        E element;
        Node<E> next;

        public Node() {
            this(null);
        }

        public Node(E element) {
            this(element, null);
        }

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }

        @Override
        public String toString() {
            return element + "_" + (next == null ? "-1" : next.element);
        }
    }

    public Node<E> addFirst(E e) {
        Node<E> newNode = new Node<>(e);
        newNode.next = dummyHead.next;
        dummyHead.next = newNode;
        size++;
        return dummyHead;
    }

    public void add(int index, E e) {
        checkRangeAdd(index);
        Node<E> prev = index == 0 ? dummyHead : node(index - 1);
        prev.next = new Node<>(e, prev.next);
        size++;
    }

    public Node<E> node(int index) {
        checkRange(index);
        Node<E> node = dummyHead;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    public void checkRange(int index) {
        if (index < 0 || index >= size) {
            throw new OutOfMemoryError("索引不能大于等于size");
        }
    }

    public void checkRangeAdd(int index) {
        if (index < 0 || index > size) {
            throw new OutOfMemoryError("索引不能大于size");
        }
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("LinkedList size=%d\n", size));
        for (Node<E> current = dummyHead.next; current != null; current = current.next) {
            res.append(current).append("->");
        }
        res.append("NULL");
        return res.toString();
    }
}
